/*
 * @lc app=leetcode.cn id=438 lang=java
 *
 * [438] 找到字符串中所有字母异位词
 */

// @lc code=start
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map.Entry;
import java.util.Set;

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int n = p.length();
        char[] pArray = p.toCharArray();
        Arrays.sort(pArray);
        String pString = new String(pArray);
        ArrayList<Integer> ans = new ArrayList<>();
        // 使用HashMap存储每个排序后的子串及其索引列表
        HashMap<String, List<Integer>> hm = new HashMap<>();

        for (int i = 0; i <= s.length() - p.length(); i++) {
            String str = s.substring(i, i + n);
            char[] charArray = str.toCharArray();
            Arrays.sort(charArray);
            String string = new String(charArray);

            // 如果HashMap中没有该键，则初始化一个列表
            if (!hm.containsKey(string)) {
                hm.put(string, new ArrayList<>());
            }
            // 将当前索引加入到对应的列表中
            hm.get(string).add(i);
        }
        // 遍历HashMap，找到所有符合条件的索引
        if (hm.containsKey(pString)) {
            ans.addAll(hm.get(pString));
        }
        return ans;
    }
}

// @lc code=end
